package algorithm.disjoint.union;

/**
 * 项目名称: god
 * 包 名 称: algorithm.disjoint.union
 * 类 名 称: UnionFindQuickUnionRankPathHalve
 * 类 描 述: TODO
 * 创建时间: 2020/6/30 3:18 下午
 * 创 建 人: Justice
 * Quick Union - 基于rank的优化 - 路径减半(Path Halve)
 */
public class UnionFindQuickUnionRankPathHalve extends UnionFindQuickUnionRank {
    public UnionFindQuickUnionRankPathHalve(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        while (v != parents[v]) {
            parents[v] = parents[parents[v]];
            v = parents[v];
        }
        return v;
    }
}
